{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number Of 2s In Range LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOf2sInRange"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #2出现的次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>编写一个方法，计算从 0 到 n (含 n) 中数字 2 出现的次数。</p>\n",
    "\n",
    "<p><strong>示例:</strong></p>\n",
    "\n",
    "<pre><strong>输入: </strong>25\n",
    "<strong>输出: </strong>9\n",
    "<strong>解释: </strong>(2, 12, 20, 21, 22, 23, 24, 25)(注意 22 应该算作两次)</pre>\n",
    "\n",
    "<p>提示：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n &lt;= 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-2s-in-range-lcci](https://leetcode.cn/problems/number-of-2s-in-range-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-2s-in-range-lcci](https://leetcode.cn/problems/number-of-2s-in-range-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.arr = {}\n",
    "    def fun(self,n):\n",
    "        if n in self.arr:\n",
    "            return self.arr[n]\n",
    "        if n == 10:\n",
    "            self.arr[n] = 1\n",
    "        else:\n",
    "            self.arr[n] = int(n / 10 + 10 * self.fun(n / 10))\n",
    "        return self.arr[n]\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "\n",
    "        num = n\n",
    "        if num<2: return 0\n",
    "        if num<10:return 1\n",
    "        _num = num\n",
    "        _num_list = []\n",
    "        while num > 0:\n",
    "            _num_list.append(num % 10)\n",
    "            num //= 10\n",
    "        _num_list = _num_list[::-1]\n",
    "        _len = len(_num_list)\n",
    "        ans = 0\n",
    "        if _num_list[0] == 2:\n",
    "            ans += _num%(10**(_len-1))+1\n",
    "        elif _num_list[0] > 2:\n",
    "            ans += 10**(_len-1)\n",
    "        ans += _num_list[0] * self.fun(10**(_len-1)) + self.numberOf2sInRange(_num%(10**(_len-1)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        digit, res = 1, 0\n",
    "        high, cur, low = n // 10, n % 10, 0\n",
    "        while high != 0 or cur != 0:\n",
    "            if cur <= 1: res += high * digit\n",
    "            elif cur == 2: res += high * digit + low + 1\n",
    "            else: res += (high + 1) * digit\n",
    "            low += cur * digit\n",
    "            cur = high % 10\n",
    "            high //= 10\n",
    "            digit *= 10\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "\n",
    "        s=str(n)\n",
    "\n",
    "        @cache\n",
    "        def f(i,cnt1,isLimit:bool):\n",
    "            if i == len(s):\n",
    "                return cnt1\n",
    "            res = 0\n",
    "            up = int(s[i]) if isLimit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt1 + (d == 2), isLimit and d == up)\n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        ep = 0\n",
    "        e = 0\n",
    "        while n:\n",
    "            ans += n // 10 * 10**e\n",
    "            if n%10 > 2:\n",
    "                ans += 10**e\n",
    "            elif n%10 == 2:              \n",
    "                ans += ep + 1\n",
    "            ep += n%10 * 10**e\n",
    "            e += 1\n",
    "            n //= 10\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        if n <= 9:\n",
    "            return 1 if n >= 2 else 0\n",
    "        pre = [0, 1, 20, 300, 4000, 50000, 600000, 7000000, 80000000, 900000000]\n",
    "        arr = str(n)\n",
    "        cnt = int(arr[0]) * pre[len(arr) - 1]\n",
    "        if arr[0] >= '2':\n",
    "            cnt += int(min(arr, '2'.ljust(len(arr), '9'))) - int('2'.ljust(len(arr), '0')) + 1\n",
    "        return cnt + self.numberOf2sInRange(int(arr[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        a = n\n",
    "        lst = [0]\n",
    "        while a>0:\n",
    "            lst.append(a%10)\n",
    "            a = a // 10\n",
    "        \n",
    "        ans = 0\n",
    "        temp = 1\n",
    "        for i in range(1,len(lst)):\n",
    "            temp +=  10**(i-2)*lst[i-1]\n",
    "            ans+= int((i-1) * (10 ** (i-2)) * lst[i])\n",
    "            if lst[i]>=3:\n",
    "                ans += int(10 ** (i-1))\n",
    "            elif lst[i] == 2:\n",
    "                ans += int(temp)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(indx, limit):\n",
    "            if indx == -1:\n",
    "                return 0\n",
    "            res, k = 0, n//(10**indx)%10\n",
    "            for i in range(k+1 if limit else 10):\n",
    "                res += f(indx-1, limit and i==k)\n",
    "                if i == 2:\n",
    "                    res += n%(10**indx)+1 if limit and k == 2 else 10**indx\n",
    "            return res\n",
    "        return f(len(str(n))-1, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i:int,is_limit:bool,res:int)->int:\n",
    "            if i==len(s):\n",
    "                return res\n",
    "            ans = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up+1):\n",
    "                ans += f(i+1,is_limit and d==up,res+(d==2))\n",
    "            return ans\n",
    "        return f(0,True,0)        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i:int,k:int,is_limit:int,is_num:int)->int:\n",
    "            if i == len(s):\n",
    "                return k\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += f(i+1,k,False,False)\n",
    "            low = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for j in range(low,up+1):\n",
    "                res += f(i+1,k+(1 if j == 2 else 0),is_limit and j == up, True)\n",
    "            return res\n",
    "        return f(0,0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int,cnt2: int,is_limit: bool)->int:\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up+1):\n",
    "                res += f(i+1,cnt2 + (d == 2),is_limit and d == up)\n",
    "            return res\n",
    "        \n",
    "        return f(0,0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, cnt2, is_limit):\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9  # 不跳过，在i位填入数字\n",
    "            for d in range(up+1):\n",
    "                res += dfs(i + 1, cnt2 + (d==2), is_limit and d == up)\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        ep = 0\n",
    "        e = 0\n",
    "        while n:\n",
    "            ans += n // 10 * 10**e\n",
    "            if n%10 > 2:\n",
    "                ans += 10**e\n",
    "            elif n%10 == 2:              \n",
    "                ans += ep + 1\n",
    "            ep += n%10 * 10**e\n",
    "            e += 1\n",
    "            n //= 10\n",
    "            \n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, cnt2: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt2 + (d == 2), is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        # 按位數計算，如125\n",
    "        # 个位5 > 2, 故2出现在个位时的次数有：12 + 1 = 13, 其中多加1表示个位为 2 时的情况\n",
    "        # 十位2 == 2, 故2出现在十位时的次数有：10 + 5 + 1 = 16\n",
    "        # 百位1 < 2, 故2不可能出现\n",
    "        p = 1           # 当前到达位数\n",
    "        res = 0\n",
    "        while p <= n:\n",
    "            L = n // (10*p)           # 取左边值 12, 1\n",
    "            R = n % (10*p)            # 取余数5, 25, 125...\n",
    "            tmp = R // p            # 取当前位5, 2, 1\n",
    "            if tmp > 2:\n",
    "                res += p\n",
    "            elif tmp == 2:\n",
    "                res += 1 + R % p\n",
    "            else:\n",
    "                pass\n",
    "            res += L*p\n",
    "            p *= 10\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def fun(self,n):\n",
    "        if n == 10: return 1\n",
    "        return int(n / 10 + 10 * self.fun(n / 10))\n",
    "\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "\n",
    "        num = n\n",
    "        if num<2: return 0\n",
    "        if num<10:return 1\n",
    "        _num = num\n",
    "        _num_list = []\n",
    "        while num > 0:\n",
    "            _num_list.append(num % 10)\n",
    "            num //= 10\n",
    "        _num_list = _num_list[::-1]\n",
    "        _len = len(_num_list)\n",
    "        ans = 0\n",
    "        if _num_list[0] == 2:\n",
    "            ans += _num%(10**(_len-1))+1\n",
    "        elif _num_list[0] > 2:\n",
    "            ans += 10**(_len-1)\n",
    "        ans += _num_list[0] * self.fun(10**(_len-1)) + self.numberOf2sInRange(_num%(10**(_len-1)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        res,i = 0,0\n",
    "        while n>10**i:\n",
    "            res+=n//(10**(i+1))*(10**(i))\n",
    "            tmp = n%(10**(i+1))//(10**i)\n",
    "            if tmp>2:\n",
    "                res+=10**i\n",
    "            elif tmp==2:\n",
    "                res+=n%(10**i)+1\n",
    "            i+=1\n",
    "        return int(n>=2) if res==0 else res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, cnt, islimit, isnum):\n",
    "            if i == len(s):\n",
    "                return cnt\n",
    "            res = 0\n",
    "            if isnum == False:\n",
    "                res += dfs(i + 1, cnt, False, False)\n",
    "            up = int(s[i]) if islimit else 9\n",
    "            for j in range(0 if isnum else 1, up + 1):\n",
    "                res += dfs(i + 1, cnt + (j == 2), islimit and (j == up), True)\n",
    "            return res\n",
    "        return dfs(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "\n",
    "        s=str(n)\n",
    "\n",
    "        @cache\n",
    "        def f(i,cnt1,isLimit:bool):\n",
    "            if i == len(s):\n",
    "                return cnt1\n",
    "            res = 0\n",
    "            up = int(s[i]) if isLimit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt1 + (d == 2), isLimit and d == up)\n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, cnt, is_limit):\n",
    "            if i == len(s):\n",
    "                return cnt\n",
    "            res = 0\n",
    "            \n",
    "            # 是合法数字\n",
    "            high = int(s[i]) if is_limit else 9\n",
    "            for j in range(high + 1):\n",
    "                if j == 2:\n",
    "                    res += dfs(i + 1, cnt + 1, is_limit and j == high)\n",
    "                else:\n",
    "                    res += dfs(i + 1, cnt, is_limit and j == high)\n",
    "            return res\n",
    "        return dfs(0, 0, True)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import functools\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        n = str(n)\n",
    "        @functools.cache\n",
    "        def dp(p: int, cnt: int = 0, limit: bool = True):\n",
    "            if p == len(n):\n",
    "                return cnt\n",
    "            \n",
    "            res = 0\n",
    "            upper = int(n[p]) if limit else 9\n",
    "            for i in range(upper + 1):\n",
    "                res += dp(p + 1, cnt + (i == 2), limit and i == upper)\n",
    "            return res\n",
    "            \n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, cnt, islimit) :\n",
    "            if i == len(s) :\n",
    "                return cnt\n",
    "            res = 0\n",
    "            up = int(s[i]) if islimit else 9 \n",
    "            for d in range(up + 1) :\n",
    "                res += dfs(i + 1, cnt + (d == 2), islimit and d == int(s[i]))\n",
    "            return res \n",
    "        return dfs(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        num2 = 0\n",
    "        left, right = n, 0\n",
    "        unit = 1\n",
    "        while left != 0:\n",
    "            digit = left % 10\n",
    "            left //= 10\n",
    "            if digit < 2:\n",
    "                num2 += left * unit\n",
    "            elif digit == 2:\n",
    "                num2 += left * unit + right + 1\n",
    "            else:\n",
    "                num2 += (left + 1) * unit\n",
    "            right += digit * unit\n",
    "            unit *= 10\n",
    "        return num2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "\n",
    "        s=str(n)\n",
    "\n",
    "        @cache\n",
    "        def f(i,cnt1,isLimit:bool):\n",
    "            if i == len(s):\n",
    "                return cnt1\n",
    "            res = 0\n",
    "            up = int(s[i]) if isLimit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt1 + (d == 2), isLimit and d == up)\n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        n = list(str(n))\n",
    "        l = len(n)\n",
    "        for i in range(l):\n",
    "            n[i] = int(n[i])\n",
    "        @cache\n",
    "        def dfs(i,flag):\n",
    "            if i == l:\n",
    "                return 0\n",
    "            if flag:\n",
    "                maxnum= n[i]\n",
    "            else:\n",
    "                maxnum = 9\n",
    "            res = 0\n",
    "            for j in range(0,maxnum+1):\n",
    "                flagj = flag & True if j == maxnum else False\n",
    "                res += dfs(i+1,flagj)\n",
    "                if j == 2:\n",
    "                    if flagj:\n",
    "                        # print(n[i+1:l])\n",
    "                        if n[i+1:l]:\n",
    "                            # t =\n",
    "                            res += int(\"\".join([str(ni) for ni in n[i+1:l]])) + 1\n",
    "                        else:\n",
    "                            res += 1\n",
    "                    else:\n",
    "                        res += 10**(l-i-1)\n",
    "                if i ==0:\n",
    "                    print(j,flagj,res)\n",
    "            return  res\n",
    "        return dfs(0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @lru_cache(None)\n",
    "        def f(i, total, is_limit):\n",
    "            if i == len(s):\n",
    "                return total\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):\n",
    "                res += f(i+1, total + (d == 2), is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        k = 10**9\n",
    "        count = 0\n",
    "        cur_sum = 0\n",
    "\n",
    "        while k:\n",
    "            cur_place = n//k%10 \n",
    "            if cur_place > 2:\n",
    "                count += (cur_sum+1) * k\n",
    "            elif cur_place < 2:\n",
    "                count += cur_sum * k\n",
    "            else:\n",
    "                count += cur_sum * k + (n%k) + 1\n",
    "            cur_sum = cur_sum*10 +cur_place\n",
    "            k//=10\n",
    "        return count\n",
    "            \n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "         \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        res,i = 0,0\n",
    "        while n>10**i:\n",
    "            res+=n//(10**(i+1))*(10**(i))\n",
    "            tmp = n%(10**(i+1))//(10**i)\n",
    "            if tmp>2:\n",
    "                res+=10**i\n",
    "            elif tmp==2:\n",
    "                res+=n%(10**i)+1\n",
    "            i+=1\n",
    "        return int(n>=2) if res==0 else res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        count = 0\n",
    "        factor = 1\n",
    "\n",
    "        while n // factor > 0:\n",
    "            curr_digit = (n // factor) % 10\n",
    "            high_part = n // (factor * 10)\n",
    "            low_part = n % factor\n",
    "\n",
    "            if curr_digit < 2:\n",
    "                count += high_part * factor\n",
    "            elif curr_digit == 2:\n",
    "                count += high_part * factor + low_part + 1\n",
    "            else:\n",
    "                count += (high_part + 1) * factor\n",
    "\n",
    "            factor *= 10\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        k = 10**9\n",
    "\n",
    "        count = 0\n",
    "        cur_sum = 0\n",
    "\n",
    "        while k:\n",
    "            cur_place = n//k%10 \n",
    "            if cur_place > 2:\n",
    "                count += (cur_sum+1) * k\n",
    "            elif cur_place == 2:\n",
    "                count += cur_sum * k + (n%k) + 1\n",
    "            elif cur_place < 2:\n",
    "                count += cur_sum * k\n",
    "            cur_sum = cur_sum*10 +cur_place\n",
    "            k//=10\n",
    "        return count\n",
    "            \n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "         \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        num = str(n)\n",
    "        N = len(num)\n",
    "\n",
    "        # [i][j]：i位(1~N)，以j开始的数(0~9, 10为和)\n",
    "        l_num = [0] * (N + 1)\n",
    "\n",
    "        # i = 1\n",
    "        l_num[1] = [0] * 11\n",
    "        l_num[1][2] = 1\n",
    "        l_num[1][-1] = 1\n",
    "\n",
    "        # 其他i\n",
    "        for i in range(2, N + 1):\n",
    "            l_num[i] = [l_num[i - 1][-1]] * 11\n",
    "            l_num[i][2] += 10 ** (i - 1)\n",
    "            l_num[i][-1] = l_num[i - 1][-1] * 10 + 10 ** (i - 1)\n",
    "\n",
    "        # N-1位直接加\n",
    "        ret = l_num[N - 1][-1] if N > 1 else 0\n",
    "\n",
    "        num2 = 0\n",
    "\n",
    "        # N位从前往后计算\n",
    "        for i in range(N):\n",
    "            n = int(num[i])\n",
    "\n",
    "            # 第一位不能等于0，其他可以\n",
    "            # 最后一位可以等于n，其他不行\n",
    "            for j in range(1 if i == 0 else 0, n if i != N - 1 else n + 1):\n",
    "                ret += l_num[N - i][j] + num2 * 10 ** (N - i - 1)\n",
    "\n",
    "            if n == 2:\n",
    "                num2 += 1\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @lru_cache(None)\n",
    "        def f(i, total, is_limit):\n",
    "            if i == len(s):\n",
    "                return total\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):\n",
    "                res += f(i+1, total + (d == 2), is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n) \n",
    "\n",
    "        @lru_cache\n",
    "        def func(i: int, cnt2: int, is_limit: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return cnt2 \n",
    "            \n",
    "            res = 0\n",
    "            max_d = int(s[i]) if is_limit else 9\n",
    "            for d in range(max_d + 1):\n",
    "                res += func(i+1, cnt2 + (d==2), is_limit and d==max_d)\n",
    "            return res \n",
    "        \n",
    "        return func(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, cnt2: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt2 + (d == 2), is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "\n",
    "        count = 0\n",
    "        factor = 1  # 位数因子，初始为个位\n",
    "        remainder = n  # 余数，初始为 n\n",
    "\n",
    "        while remainder > 0:\n",
    "            current_digit = remainder % 10  # 获取当前位的数字\n",
    "            remainder //= 10  # 更新余数\n",
    "\n",
    "            count += remainder * factor  # 计算当前位之前的数字对当前位产生的 2 的贡献\n",
    "            if current_digit > 2:\n",
    "                count += factor  # 当前位大于 2，该位上的 2 出现的次数为当前位的 10 的位数\n",
    "\n",
    "            if current_digit == 2:\n",
    "                count += n % factor + 1  # 当前位等于 2，需要考虑当前位后面的数字对当前位产生的 2 的贡献\n",
    "\n",
    "            factor *= 10  # 更新位数因子\n",
    "\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        num = str(n)\n",
    "        @cache\n",
    "        def dfs(u, count, is_limit, is_num):\n",
    "            if u == len(num):\n",
    "                return count\n",
    "            res = 0\n",
    "            if not is_num: res = dfs(u + 1, count, False, False)\n",
    "            up = int(num[u]) if is_limit else 9\n",
    "            for i in range(1 - int(is_num), up + 1):\n",
    "                res += dfs(u + 1, count + (i == 2), is_limit and i == up, True)\n",
    "            return res\n",
    "        return dfs(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        k = 1\n",
    "        while k <= n:\n",
    "            ans += (n//(10 * k)) * k + min(k,max(n % (10 * k) - 2 * k + 1,0))\n",
    "            k *= 10 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache  # 记忆化搜索\n",
    "        def f(i: int, mask: int, is_limit: bool, is_num: bool) -> int:      #这里mask用来统计到当前数位i总共填了多少个2\n",
    "            if i == len(s):\n",
    "                return mask if is_num else 0  # is_num 为 True 表示得到了一个合法数字\n",
    "            res = 0\n",
    "            if not is_num:  # 可以跳过当前数位\n",
    "                res = f(i + 1, mask, False, False)\n",
    "            low = 0 if is_num else 1  # 如果前面没有填数字，必须从 1 开始（因为不能有前导零）\n",
    "            up = int(s[i]) if is_limit else 9  # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            for d in range(low, up + 1):  # 枚举要填入的数字 d\n",
    "                if d == 2:\n",
    "                    res += f(i + 1, mask + 1, is_limit and d == up, True)\n",
    "                else:\n",
    "                    res += f(i + 1, mask, is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        def solve(s:str)->int:#便于取片\n",
    "            @cache\n",
    "            def f(i: int, is_limit : bool, is_num : bool)->int:\n",
    "                if i==len(s):\n",
    "                    return 0\n",
    "                res=0\n",
    "                if not is_num:\n",
    "                    res +=f(i+1,False,False)\n",
    "                low=0 if is_num else 1\n",
    "                up=int(s[i]) if is_limit else 9\n",
    "                for d in range(low,up+1):\n",
    "                    if d==2:\n",
    "                        cnt=1\n",
    "                        if is_limit and d==up:\n",
    "                            if i+1<len(s): cnt +=int(s[i+1:])\n",
    "                        else:\n",
    "                            cnt=10**(len(s)-i-1)\n",
    "                        res +=cnt\n",
    "                    res +=f(i+1, is_limit and d==up, True)\n",
    "                return res\n",
    "\n",
    "            return f(0,True,False)\n",
    "        return solve(str(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        count, factor, digit = 0, 1, 0\n",
    "        \n",
    "        # Working with the least significant digit and moving towards the most significant digit\n",
    "        while n // factor > 0:\n",
    "            lower_num = n - (n // factor) * factor  # Lower part of n\n",
    "            curr_digit = (n // factor) % 10         # Current digit\n",
    "            higher_num = n // (factor * 10)         # Higher part of n\n",
    "            \n",
    "            # If the current digit is greater than 2, count all 2's that can appear at this digit's place\n",
    "            if curr_digit > 2:\n",
    "                count += (higher_num + 1) * factor\n",
    "            # If the current digit is 2, count the 2's from higher part and also all the numbers from 0 to lower_num\n",
    "            elif curr_digit == 2:\n",
    "                count += higher_num * factor + lower_num + 1\n",
    "            # If the current digit is less than 2, count the 2's only from the higher part\n",
    "            else:\n",
    "                count += higher_num * factor\n",
    "            \n",
    "            factor *= 10\n",
    "        \n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "         \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, cnt2: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt2 + (d == 2), is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        length=len(s)\n",
    "        @cache\n",
    "        def f(i,count,isLimited):\n",
    "            if(i==length):\n",
    "                return count\n",
    "            limit=int(s[i]) if isLimited else 9\n",
    "            ans=0\n",
    "            for j in range(0,limit+1):\n",
    "                ans+=f(i+1,count+(1 if j==2 else 0),isLimited and j==limit)\n",
    "            return ans\n",
    "        return f(0,0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i, count1, is_limit):\n",
    "            if i == len(s):\n",
    "                return count1 \n",
    "            res = 0\n",
    "\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "\n",
    "            for d in range(0, up + 1):\n",
    "                res += f(i + 1, count1 + int(d == 2), is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(u, limit, is_num):\n",
    "            if u == m:\n",
    "                return 0\n",
    "            ans = 0\n",
    "            if is_num == False:\n",
    "                ans += dfs(u+1, False, False)\n",
    "\n",
    "            st = 0 if is_num else 1\n",
    "            end = int(s[u]) if limit else 9\n",
    "            if 2 < end:\n",
    "                ans += pow(10, m - 1 - u)\n",
    "            elif 2 == end and limit:\n",
    "                ans += int(s[u+1:]) + 1 if u+1 < m else 1\n",
    "            for i in range(st, end + 1):\n",
    "                # if i == 2:\n",
    "                #     ans += pow(10, m - u - 1) if limit == False else (int(s[u+1:]) + 1 if u+1 < m else 1)\n",
    "                ans += dfs(u+1, limit and i == end, True)\n",
    "            return ans\n",
    "\n",
    "        s = str(n)\n",
    "        m = len(s)\n",
    "        return dfs(0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        \n",
    "        cache = {}\n",
    "\n",
    "        def f(i: int, cnt2: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            if (i, cnt2, is_limit) in cache:\n",
    "                return cache[(i, cnt2, is_limit)]\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt2 + (d == 2), is_limit and d == up)\n",
    "            \n",
    "            cache[(i, cnt2, is_limit)] = res \n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i: int, c: int, l: bool) -> int:\n",
    "            if i == n:\n",
    "                return c\n",
    "            up = int(s[i]) if l else 9\n",
    "            res = 0\n",
    "            for d in range(up + 1):\n",
    "                if d == 2:\n",
    "                    res += dfs(i + 1, c + 1, l and up == d)\n",
    "                else:\n",
    "                    res += dfs(i + 1, c, l and up == d)\n",
    "            return res\n",
    "        return dfs(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        arr=[1]\n",
    "        for i in range(2,10):\n",
    "            arr.append(arr[-1]*10+10**(i-1))\n",
    "        p=len(str(n))\n",
    "        ans=0\n",
    "        def check(s):\n",
    "            nonlocal ans\n",
    "            if len(s)==1:\n",
    "                if int(s[0])>=2:\n",
    "                    ans+=1\n",
    "                return \n",
    "            if s[0]<'2':\n",
    "                ans+=int(s[0])*arr[len(s)-2]\n",
    "                check(s[1::])\n",
    "            elif s[0]=='2':\n",
    "                ans+=int(s[0])*arr[len(s)-2]+int(s[1::])+1\n",
    "                check(s[1::])\n",
    "            else:\n",
    "                ans+=int(s[0])*arr[len(s)-2]+10**(len(s)-1)\n",
    "                check(s[1::])\n",
    "        check(str(n))\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n) \n",
    "\n",
    "        @lru_cache\n",
    "        def func(i: int, cnt2: int, is_limit: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return cnt2 \n",
    "            \n",
    "            res = 0\n",
    "            max_d = int(s[i]) if is_limit else 9\n",
    "            for d in range(max_d + 1):\n",
    "                res += func(i+1, cnt2 + (d==2), is_limit and d==max_d)\n",
    "            return res \n",
    "        \n",
    "        return func(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i: int, cnt1: int, is_limit: bool, is_num: bool):\n",
    "            if i == len(s):\n",
    "                return cnt1\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = dfs(i + 1, cnt1, False, False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(1 - int(is_num), up + 1):\n",
    "                res += dfs(i + 1, cnt1 + (d == 2), is_limit and d == up, True)\n",
    "            return res\n",
    "        return dfs(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        digits = len(str(n))\n",
    "        k = 10**(digits-1)\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        while k:\n",
    "            cur_place = n//k%10 \n",
    "            if cur_place > 2:\n",
    "                count += (n//(k*10)+1) * k\n",
    "            elif cur_place == 2:\n",
    "                count += (n//(k*10)) * k + (n%k) + 1\n",
    "            elif cur_place < 2:\n",
    "                count += (n//(k*10)) * k\n",
    "            \n",
    "            k//=10\n",
    "        return count\n",
    "            \n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "         \n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def dfs(i: int, c: int, l: bool) -> int:\n",
    "            if i == n:\n",
    "                return c\n",
    "            up = int(s[i]) if l else 9\n",
    "            res = 0\n",
    "            for d in range(up + 1):\n",
    "                res += dfs(i + 1, c + int(d == 2), l and up == d)\n",
    "            return res\n",
    "        return dfs(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s= str(n) \n",
    "        x= 2\n",
    "        count = 0\n",
    "        for i in range(len(s)):\n",
    "            current = int(s[i])\n",
    "            high = 0 if s[:i]=='' else int(s[:i])\n",
    "            low =0 if s[i+1:]=='' else int(s[i+1:])\n",
    "            if current>x:\n",
    "                count+=(high+1)*(10**len(s[i+1:]))\n",
    "            elif current<x:\n",
    "                count += (high) * (10 ** len(s[i + 1:]))\n",
    "            else:\n",
    "                count +=(high) * (10 ** len(s[i + 1:]))+low+1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        \n",
    "        # cache = {}\n",
    "        @cache\n",
    "        def f(i: int, cnt2: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            #if (i, cnt2, is_limit) in cache:\n",
    "            #    return cache[(i, cnt2, is_limit)]\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt2 + (d == 2), is_limit and d == up)\n",
    "            \n",
    "            # cache[(i, cnt2, is_limit)] = res \n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, cnt2: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt2 + (d == 2), is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        \n",
    "        cache = {}\n",
    "        \n",
    "        def f(i: int, cnt2: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            if (i, cnt2, is_limit) in cache:\n",
    "                return cache[(i, cnt2, is_limit)]\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt2 + (d == 2), is_limit and d == up)\n",
    "            \n",
    "            cache[(i, cnt2, is_limit)] = res \n",
    "            return res\n",
    "            \n",
    "        return f(0, 0, True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "\n",
    "        @cache \n",
    "        def f(i: int, cnt:int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt \n",
    "            res = 0 \n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up+1):\n",
    "                res += f(i+1, cnt + (d==2), is_limit and (d==up))\n",
    "            return res \n",
    "        return f(0,0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        \n",
    "        # cache = {}\n",
    "        @cache\n",
    "        def f(i: int, cnt2: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            #if (i, cnt2, is_limit) in cache:\n",
    "            #    return cache[(i, cnt2, is_limit)]\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt2 + (d == 2), is_limit and d == up)\n",
    "            \n",
    "            # cache[(i, cnt2, is_limit)] = res \n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        res,i = 0,0\n",
    "        while n>10**i:\n",
    "            res+=n//(10**(i+1))*(10**(i))\n",
    "            tmp = n%(10**(i+1))//(10**i)\n",
    "            if tmp>2:\n",
    "                res+=10**i\n",
    "            elif tmp==2:\n",
    "                res+=n%(10**i)+1\n",
    "            i+=1\n",
    "        return int(n>=2) if res==0 else res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, cnt, is_limit, is_num):\n",
    "            if i == len(s): return cnt\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = dfs(i + 1, cnt, False, False)\n",
    "            low = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(low, up + 1):\n",
    "                res += dfs(i + 1, cnt + (d == 2), is_limit and d == up, True)\n",
    "            return res\n",
    "        return dfs(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        m=len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k,is_limit):\n",
    "            if i==m:\n",
    "                return k\n",
    "            maxv=int(s[i]) if is_limit else 9\n",
    "            ans=0\n",
    "            for j in range(maxv+1):\n",
    "                ans+=dfs(i+1,k+(j==2),is_limit and j==maxv)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        @cache\n",
    "        def dfs(i,cnt,is_limit):\n",
    "            if i==len(s):\n",
    "                return cnt\n",
    "            res=0\n",
    "            \n",
    "            right=int(s[i]) if is_limit else 9\n",
    "            for d in range(right+1):\n",
    "                res+=dfs(i+1,cnt+1 if d==2 else cnt,is_limit and d==right)\n",
    "            return res\n",
    "        return dfs(0,0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int, cnt2: int, is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return cnt2\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):  # 枚举要填入的数字 d\n",
    "                res += f(i + 1, cnt2 + (d == 2), is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/number-of-2s-in-range-lcci/solutions/1750395/by-endlesscheng-x4mf/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        n = len(s)\n",
    "        @cache\n",
    "        def f(i, is_limit, is_num, cnt):\n",
    "            if i == n:\n",
    "                return cnt\n",
    "            res = 0\n",
    "            if is_num == 0:\n",
    "                res = f(i + 1, False, False, cnt)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(1 - int(is_num), up + 1):\n",
    "                res += f(i + 1,is_limit and d == up, True, cnt + (d == 2))\n",
    "            return res\n",
    "        return f(0,True, False, 0)                       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        m=len(s)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,k,is_limit):\n",
    "            if i==m:\n",
    "                return k\n",
    "            maxv=int(s[i]) if is_limit else 9\n",
    "            ans=0\n",
    "            for j in range(maxv+1):\n",
    "                ans+=dfs(i+1,k+(j==2),is_limit and j==maxv)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(0,0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        @cache\n",
    "        def dfs(num,i,ss,islimit,isnum):\n",
    "            if i==len(str(num)):\n",
    "                if isnum:\n",
    "                    return ss\n",
    "                return 0\n",
    "            res=0\n",
    "            if not isnum:\n",
    "                res+=dfs(num,i+1,ss,False,False)\n",
    "            low=0 if isnum else 1\n",
    "            up=int(str(num)[i]) if islimit else 9\n",
    "            for j in range(low,up+1):\n",
    "                if j==2:\n",
    "                    res+=dfs(num,i+1,ss+1,islimit and j==up,True)\n",
    "                else :\n",
    "                    res+=dfs(num,i+1,ss,islimit and j==up,True)\n",
    "            return res\n",
    "        return dfs(n,0,0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i:int, cnt: int, is_limit):\n",
    "            if i == len(s):\n",
    "                return cnt\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(up + 1):\n",
    "                res += f(i + 1, cnt + (d == 2), is_limit and d == up)\n",
    "            return res\n",
    "        return f(0, 0, True)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        @cache\n",
    "        def dfs(i,mask,isLimit):\n",
    "            if i==len(s):\n",
    "                return mask\n",
    "            res=0\n",
    "            up=int(s[i]) if isLimit else 9\n",
    "            for index in range(up+1):\n",
    "                res+=dfs(i+1,mask+(index==2),isLimit and index==int(s[i]))\n",
    "            return res\n",
    "        return dfs(0,0,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOf2sInRange(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        # i构造第i位及其之后数位合法的方案数\n",
    "        # cnt表示1出现次数\n",
    "        # is_limit是否受到n大小约束（当前数字必须小于n）\n",
    "        # is_num表示i前面是否填了数字\n",
    "        @cache\n",
    "        def f(i, cnt, is_limit, is_num):\n",
    "            if i == len(s):\n",
    "                return cnt\n",
    "            res = 0\n",
    "            up = int(s[i]) if is_limit else 9   # 如果前面填的数字都和 n 的一样，那么这一位至多填 s[i]（否则就超过 n 啦）\n",
    "            for d in range(up + 1):\n",
    "                res += f(i + 1, cnt + int(d == 2), is_limit and d == up, True)\n",
    "            return res\n",
    "        return f(0, 0, True, False)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
